CSE 373: Data Structures and Algorithms

Winter 2000

Midterm 1 January 31, 2000

 


Name: _____________________________________________


Student ID #: ________________________________________

 

This test consists of 12 questions each worth 10 points.



Abstract Data Types

 

#1 [10 points] 

 

Describe the purpose of an abstract data type.  Don’t tell me what it is, but instead tell me why it is useful.

 

Pointer and Natural Alignment

 

#2 [10 points] 

 

Circle the natural alignment addresses for the following variable types


char (a natural 1 byte data type)

0x100  0x101  0x102  0x103  0x104  0x105  0x106  0x107
 
0x108  0x109  0x10a  0x10b  0x10c  0x10d  0x10e  0x10f

short (a natural 2 byte data type)
 
0x100  0x101  0x102  0x103  0x104  0x105  0x106  0x107

0x108  0x109  0x10a  0x10b  0x10c  0x10d  0x10e  0x10f

long (a natural 4 byte data type)
 
0x100  0x101  0x102  0x103  0x104  0x105  0x106  0x107

0x108  0x109  0x10a  0x10b  0x10c  0x10d  0x10e  0x10f

longlong (a natural 8 byte data type)

0x100  0x101  0x102  0x103  0x104  0x105  0x106  0x107

0x108  0x109  0x10a  0x10b  0x10c  0x10d  0x10e  0x10f

 

 

Analysis

 

#3 [10 points]

 

Order the following Big-Oh values by growth rate.  From fastest to slowest (i.e., the one that takes the least amount of time to run to the longest time to run)

O(N)    O(N log N)    O(log N)    O(N2)    O(2N)    O(100)

 

Lists

 

#4 [10 points]

 

Assume you have a non-circular doubly linked list and a pointer to an arbitrary element E  in the list.  I want you to list the steps necessary to remove E from the list.  Use the following field names for the linked list structure

    typedef struct _LINKEDLIST {
        struct _LINKEDLIST *Flink;  // Forward pointer
        struct _LINKEDLIST *Blink;  // Backward pointer
    } LINKEDLIST *PLINKEDLIST;

Note that the list is non-circular.

 

 

 

 

 

 

 

 

 

 

 

 

Stacks

 

#5 [10 points] 

 

When implementing stacks using an array there are three essential elements or properties that need to be accounted for.  List these three elements, give a description of the purpose of each, and how it is used in the various stack operations.

 

Queues

 

#6 [10 points]  

 

In an array implementation of queues there is typically an index for the front of the queue (the dequeue end), an index for the back of the queue (the enqueue end), and a count of the number of elements in the queue.  Why is a count necessary and not just a luxury?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Trees

 

#7 [10 points] 

 

Circle those properties that do not belong in a general tree data structure

  1. A node can have one or more children

  2. A node with the exception of the root node can have one or more parents

  3. Cycles are not permitted

  4. A single tree edge connects multiple nodes

  5. Internal tree nodes have one or more children

 

#8 [10 points]

 

Given a binary search tree with fields LeftChild and RightChild identify the type of traversal each of the following algorithms perform


    void WhatTypeOfTraversalAmI1( NODE *ptr)
    {
        if (ptr == NULL) return;
        WhatTypeOfTraveralAmI1(ptr->LeftChild);
        printf(ptr->value);
        WhatTypeOfTraversalAmI1(ptr->RightChild);
    }

 

 

 

 

    void WhatTypeOfTraversalAmI2( NODE *ptr)
    {
        if (ptr == NULL) return;
        WhatTypeOfTraveralAmI2(ptr->LeftChild);
        WhatTypeOfTraversalAmI2(ptr->RightChild);
        printf(ptr->value);
    }

 

 

 

 

    void WhatTypeOfTraversalAmI3( NODE *ptr)
    {
        if (ptr == NULL) return;
        printf(ptr->value);
        WhatTypeOfTraversalAmI3(ptr->RightChild);
    }

 

 

 

 

    void WhatTypeOfTraversalAmI4( NODE *ptr)
    {
        if (ptr == NULL) return;
        printf(ptr->value);
        WhatTypeOfTraveralAmI4(ptr->LeftChild);
        WhatTypeOfTraversalAmI4(ptr->RightChild);
    }

#9 [10 points]

 

Given the following Binary Search tree show the results, by redrawing the tree, of inserting a new node of value 48.

                         50

 

 


    

                20              200

 


             7      47       67

 

 

#10 [10 points]

 

Given the following Binary Search tree show the results, by redrawing the tree, of deleting the node with value 200.

 

                         50

 

 


    

                20              200

 


             7      47       67         210

 

 


                         64    100   205   220

 

 

#11 [10 points]

 

In the following Binary Search Tree show the result of splaying the node ‘A’

 

                        I

 

                   H

 


              G

 


         F

 


              E

 


         D

 


              C

 


                   B

 


                        A

 

 

B-Trees

 

#12 [10 points]

 

Given the following collection of trees cross out those trees that are not legal 2-3 trees and state why they are illegal trees. trees.  In the diagrams (( E:- )) denotes a internal b-tree node and   B C D  denotes a leaf node.

 

                 

          (( E:- ))

 

 


    B C D        (( H:- ))

 

 

           E F G           H I J          

 

 

 

 

 

 

          (( D:- ))

 

 


      B C           D E

 

 

 

 

 

                          (( E:F:I ))

 

 


     B C D            E F             G H            I J

 

 

 

 

 

         (( C:- ))

 

 


       B           C D